//class Solution {
//public:
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        dfs(A, B, C, A.size());
//    }
//
//    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
//    {
//        if (n == 1)
//        {
//            C.push_back(A.back());
//            A.pop_back();
//            return;
//        }
//        dfs(A, C, B, n - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        dfs(B, A, C, n - 1);
//    }
//};



//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        if (list1 == nullptr || list2 == nullptr)
//            return list1 ? list1 : list2;
//        if (list1->val < list2->val)
//        {
//            list1->next = mergeTwoLists(list1->next, list2);
//            return list1;
//        }
//        else
//        {
//            list2->next = mergeTwoLists(list1, list2->next);
//            return list2;
//        }
//    }
//};




//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        return dfs(head);
//    }
//
//    ListNode* dfs(ListNode* head)
//    {
//        if (head == nullptr || head->next == nullptr)
//        {
//            return head;
//        }
//        ListNode* newhead = dfs(head->next);
//        head->next->next = head;
//        head->next = nullptr;
//        return newhead;
//    }
//};



//
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr)
//            return head;
//        ListNode* tmp = swapPairs(head->next->next);
//        ListNode* newhead = head->next;
//        newhead->next = head;
//        head->next = tmp;
//        return newhead;
//    }
//};



class Solution {
public:
    double myPow(double x, long long n) {
        return n < 0 ? 1.0 / dfs(x, -n) : dfs(x, n);
    }

    double dfs(double x, long long n)
    {
        if (n == 0)
            return 1.0;
        double tmp = dfs(x, n / 2);
        return n % 2 == 1 ? tmp * tmp * x : tmp * tmp;
    }
};